package 剑指offer;

import org.junit.Test;

public class _55平衡二叉树 {
	@Test
	public void test() {
	
		}
	/**
	 * 
	 *@time 2021年3月21日上午10:49:00
	 * 
	 *@param root
	 *@return boolean
	 *
	 *@see
	 *先序遍历 + 判断深度 （从顶至底）
	 *此方法容易想到，但会产生大量重复计算，时间复杂度较高。
	 *思路是构造一个获取当前子树的深度的函数 depth(root) 
	 *通过比较某子树的左右子树的深度差 abs(depth(root.left) - depth(root.right)) <= 1 是否成立，
	 *来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。
	 */
    public boolean isBalanced(TreeNode root) {
        return Math.abs(treeLength(root.left)-treeLength(root.right))<=1 
        		&&isBalanced(root.left)
        		&&isBalanced(root.right);
    }
    public int treeLength(TreeNode node){
        if(node == null) return 0;
        return Math.max(treeLength(node.left),treeLength(node.right))+1;
    }   
    	/**
    	 * 
    	 *@time 2021年3月21日上午10:48:51
    	 * 
    	 *@param root
    	 *@return boolean
    	 *
    	 *@see 
    	 *后序遍历 + 剪枝 （从底至顶）
		 *此方法为本题的最优解法，但剪枝的方法不易第一时间想到。
		 *思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
    	 */
        public boolean isBalanced1(TreeNode root) {
            return recur(root) != -1;
        }

        private int recur(TreeNode root) {
            if (root == null) return 0;
            int left = recur(root.left);
            if(left == -1) return -1;
            int right = recur(root.right);
            if(right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
        }
    


}
